#include <cstdlib>
#include <cstdio>
#include "../Basics/BasicStruct.cpp"

// 字符串匹配(t为s子串)


//1. 遍历整条s链表,对每个节点都实行一次字符串匹配.

bool getResult(ListNode *sp, ListNode *t);

// 1 2 3 4
//   2 3
ListNode* getPosNode(ListNode* s, ListNode* t) {
    ListNode* sp = s;
    // 遍历s链表
    while(sp != NULL) {
        //对每一个元素,作为开头字符串匹配一次.
        if (getResult(sp, t)) {
            // 成功返回当前节点
            return sp;
        }
        sp = sp->next;
    }
    // 失败返回null
    return NULL;
}

bool getResult(ListNode *sp, ListNode *t) {
    ListNode* p1 = sp;
    ListNode* p2 = t;
    // 双指针依次向后遍历,如果当前元素不相同则退出,或者子串走到结尾时带条成功匹配,主串结束且子串不为空,则失败.
    while(p1 != NULL && p2 != NULL && p2->data == p1->data) {
        p1 = p1->next;
        p2 = p2->next;
    }
    if (p2 != NULL) {
        return false;
    }
    return true;
}


int main() {
    List s = CreateList();
    List t = CreateList();
    ListNode* listNode = getPosNode(s,t);
    printf("%d",listNode->data);
    return 0;
}


